/*
766. 托普利茨矩阵

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。

给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。

示例 1:

输入: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
输出: True
解释:
1234
5123
9512

在上面这个矩阵中, 对角线分别是 "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", 各条对角线上的所有元素都相同, 因此答案是True。

示例 2:

输入: matrix = [[1,2],[2,2]]
输出: False
解释: 
对角线, 比如: "[1, 2]" 上有不同的元素。

注意:

     matrix (矩阵)是一个包含整数的二维数组。
    matrix 的行数和列数均在 [1, 20]范围内。
    matrix[i][j] 包含的整数在 [0, 99]范围内。
*/
#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    bool isToeplitzMatrix(vector<vector<int>> &matrix)
    {
        int m = matrix.size();
        int n = m > 0 ? matrix[0].size() : 0;
        if(n <= 1 || m <= 1) return true;
        vector<int> sum(m + n);
        for(int i = 0; i < n; i++) {
            sum[n - i] = matrix[0][i];
        }
        for(int i = 1; i < m; i++) {
            sum[n + i] = matrix[i][0];
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(sum[n - j + i] != matrix[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

int main(int argc, char *argv[])
{
    Solution    sol;
    vector<int> n1(4);
    vector<int> n2(4);
    vector<int> n3(4);
    n1[0] = 1; //[[1,2,3,4],[5,1,2,3],[9,5,1,2]]
    n1[1] = 2;
    n1[2] = 3;
    n1[3] = 4;
    n2[0] = 5;
    n2[1] = 1;
    n2[2] = 2;
    n2[3] = 3;
    n3[0] = 9;
    n3[1] = 5;
    n3[2] = 1;
    n3[3] = 2;
    vector<vector<int>> m;
    m.push_back(n1);
    m.push_back(n2);
    m.push_back(n3);

    cout << sol.isToeplitzMatrix(m) << endl;
    return 0;
}